      BOI.13. (Rotaia cilindrilor). Un sistem conex de transmisie este format
din n(n30) cilindri, numerotai de la 1 la n. Dac[ cilindrii i i j sunt n contact
unul cu altul i unul din ei se nvrte ntr-un sens (Clockwise sau Opposite), atunci
cel[lalt se rotete n sens opus. Dac[ doi cilindri aflai n contact se rotesc n
aceeai direcie, atunci sistemul se blocheaz[ (vezi Figura 1).









                                      Figura 1
Problem[:
           S[ se scrie un program care, pentru un sistem de transmisie conex dat,
determin[ comportarea lui atunci cnd un cilindru precizat se nvrte ntr-un anumit
sens: se blocheaz[ sau lucreaz[ normal.
           Dac[ transmisia lucreaz[ normal, programul listeaz[ cilindrii i sensurile
lor de rotaie. In caz contrar, programul determin[ num[rul minim de cilindri
diferii de cilindrul i care trebuiesc eliminai din angrenajul blocat, astfel nct toi
cilindrii r[mai s[ se roteasc[ la rotirea cilindrului i.
Intrare: Intrarea este un fiier ASCII cu urm[torul format:
Prima linie conine num[rul n de cilindri i num[rul m de perechi de cilindri aflai
n contact;
Fiecare din urm[toarele m linii conine o pereche de cilindri n contact;
Ultima linie conine num[rul i al cilindrului care va fi rotit i un caracter (C sau
O) care simbolizeaz[ sensul s[u de rotire. Pentru transmisiile din Figura 1 intrarea
va fi:
5 5                       respectiv3 3 
1 2                                                                                1 2
1 3                                                                                1 3
2 4                                                                                2 3
3 4                                                                                1 O
3 5
1 C
Ieire: Ieirea va fi standard (ecran) i va consta din trei sau patru linii. Prima linie
descrie comportarea sistemului printr-o liter[: W (funcioneaz[) sau B (blocat).
Dac[ sistemul funcioneaz[, atunci a doua linie este o list[ a cilindrilor care se
rotesc Clockwise, iar a treia linie este o list[ a cilindrilor care se rotesc Opposite.
Dac[ sistemul este blocat, atunci a doua linie este o list[ a cilindrilor care se rotesc
Clockwise, a treia linie este o list[ a cilindrilor care se rotesc Opposite dup[ ce a
fost eliminat num[rul minim de cilindri, iar a patra linie conine cilindrii eliminai
(Removed) dup[ formatul de scriere de mai jos:
Pentru cele dou[ exemple anterioare ieirea va fi:
W                                          B
C 1 4 5                                    C 2
O 2 3                                      O 1
                                           R 3

=================================================
            BOI 13. (Vlad Petric, elev Braov)
Ideea principal[ de lucru este backtrackingul, numai c[ parcugerea se face eficient,
adic[ dup[ ce un nod este marcat, se continu[ marcarea cu nodurile adiacente
acestuia. Cum sistemul este conex, vor fi parcurse toate nodurile.
const dim=250;
var graf:array[1..dim,1..dim] of boolean;
    dm,n,m,p:byte;
    s:char;
    sir,sm:array[1..dim] of char;
-----------------------------------------------
function posibil(p:byte;ch:char):boolean;
var i:byte;
begin
  for i:=1 to n do
    if graf[i,p] and (sir[i]=ch) then begin
      posibil:=false;
      exit;
    end;
  posibil:=true;
end;
-------------------------------------------
procedure backtrack(p,count,el:byte);
var i:byte;
begin
  if el<dm then
    if count=n  then begin
      dm:=el; sm:=sir end
    else
      for i:=1 to n do
        if (sir[i]=' ') and graf[i,p] then begin
          if posibil(i,'C') then begin
            sir[i]:='C';
            backtrack(i,count+1,el);
          end;
          if posibil(i,'O') then begin
            sir[i]:='O';
            backtrack(i,count+1,el);
          end;
          sir[i]:='R';
          backtrack(i,count+1,el+1);
          sir[i]:=' ';
        end;
end;
----------------------------------------
procedure tratare;
var i:byte;
    aux:boolean;
begin
  sir[p]:=s; dm:=n;
  backtrack(p,1,0);
  sir:=sm; aux:=true;
  for i:=1 to n do
    if sir[i]='R' then aux:=false;
  if aux then writeln('W')
         else writeln('B');
  write('C ');
  for i:=1 to n do
    if sir[i]='C' then
      write(i,' '); writeln; write('O ');
  for i:=1 to n do
    if sir[i]='O' then write(i,' ');
  writeln;
  if not aux then begin
    write('R ');
    for i:=1 to n do
      if sir[i]='R' then write(i,' ');
    writeln;
  end;
end;
----------------------------------------------
procedure citire;
var f:text;
    nf:string;
    i,j,a,b:byte;
    ss:char;
begin
  writeln('Nume fisier:'); readln(nf);
  assign(f,nf); reset(f); readln(f,n,m);
  for i:=1 to n do begin
    sir[i]:=' ';
    for j:=1 to n do
      graf[i,j]:=false;
  end;
  for i:=1 to m do begin
    readln(f,a,b); graf[a,b]:=true; graf[b,a]:=true;
  end;
  readln(f,p,ss,s); close(f);
end;
--------------------------------
begin {Program principal}
  citire;
  tratare;
end.
============================================
